{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "\n",
    "快速排序\n",
    "\n",
    "### 介绍：\n",
    "\n",
    "    快速排序通常明显比同为Ο(n log n)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可见掌握快排的重要性。\n",
    "\n",
    "\n",
    "### 步骤：\n",
    "\n",
    "    从数列中挑出一个元素作为基准数。\n",
    "    分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。\n",
    "    再对左右区间递归执行第二步，直至各区间只有一个数。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def quick_sort(b):\n",
    "    \"\"\"快速排序\"\"\"\n",
    "    if len(b) < 2:\n",
    "        return b\n",
    "    # 选取基准，随便选哪个都可以，选中间的便于理解\n",
    "#     mid = b[len(b) // 2]\n",
    "    # 定义基准值左右两个数列\n",
    "    left, right = [], []\n",
    "    # 从原始数组中移除基准值\n",
    "    mid = b.pop()\n",
    "    for item in b:\n",
    "        # 大于基准值放右边\n",
    "        if item >= mid:\n",
    "            right.append(item)\n",
    "        else:\n",
    "            # 小于基准值放左边\n",
    "            left.append(item)\n",
    "    # 使用迭代进行比较\n",
    "    return quick_sort(left) + [mid] + quick_sort(right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def quick_sort2(nums):\n",
    "    return qsort(nums, 0, len(nums) - 1)\n",
    "\n",
    "\n",
    "def qsort(nums, start, end):\n",
    "    if start < end:\n",
    "        left = start  # 左右两个指针，左指针标识分隔的位置。\n",
    "        right = end\n",
    "        key = nums[start]  # 选择第一个作为基数\n",
    "#         print('key',key)\n",
    "    else:\n",
    "        # 前一轮已经基本有序了\n",
    "        return nums\n",
    "    while left < right:\n",
    "        while left < right and nums[right] >= key:\n",
    "            right -= 1\n",
    "        if left < right:  \n",
    "            # 说明打破while循环的原因是ary[right] <= key\n",
    "            nums[left] = nums[right]\n",
    "            left += 1\n",
    "        while left < right and nums[left] < key:\n",
    "            left += 1\n",
    "        if left < right:  \n",
    "            # 说明打破while循环的原因是ary[left] >= key\n",
    "            nums[right] = nums[left]\n",
    "            right -= 1\n",
    "    nums[left] = key  # 此时，left=right，用key来填坑\n",
    "#     print('start', start)\n",
    "#     print('left', left)\n",
    "#     print('end', end)\n",
    "#     print(nums)\n",
    "#     print('nums[start: left - 1]',nums[start: left - 1])\n",
    "    qsort(nums, start, left - 1)  # left 位置是基数，不参与了\n",
    "#     print('nums',nums)\n",
    "    \n",
    "#     print('nums[left + 1: end]',nums[left + 1: end])\n",
    "    qsort(nums, left + 1, end)\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nums = [1,4,8,3,7,2,5,9,6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quick_sort2(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "quick_sort  0.08445159999973839 ms\n",
      "quick_sort2 0.07396199999948294 ms\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "\n",
    "print(\"quick_sort \",timeit.timeit(\"quick_sort([1,4,8,3,7,2,5,9,6])\", setup=\"from __main__ import quick_sort\", number=10000), \"ms\")\n",
    "print(\"quick_sort2\",timeit.timeit(\"quick_sort2([1,4,8,3,7,2,5,9,6])\", setup=\"from __main__ import quick_sort2\", number=10000), \"ms\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "quick_sort(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
